---
id: 5900f5171000cf542c510029
title: 'Завдання 426: система коробок та м’ячів'
challengeType: 1
forumTopicId: 302096
dashedName: problem-426-box-ball-system
---

# --description--

Розглянемо нескінченний ряд коробок. У деяких коробках є м’яч. Наприклад, початкове розташування 2 послідовних заповнених коробок, після яких йдуть 2 порожні коробки, 2 заповнені коробки, 1 порожня коробка та 2 заповнені коробки, можна записати як послідовність (2, 2, 2, 1, 2), де кількість відповідних заповнених та порожніх коробок відображається послідовно.

Хід складається з переміщення кожного м’яча один раз за таким правилом: перенесіть найлівіший м’яч, який не переміщали, до найближчої порожньої коробки справа.

Як можна побачити нижче, після одного ходу послідовність (2, 2, 2, 1, 2) стає послідовністю (2, 2, 1, 2, 3). Зверніть увагу, що нова послідовність починається з першої заповненої коробки.

<img class="img-responsive center-block" alt="анімація завершеного ходу з (2, 2, 2, 1, 2) до (2, 2, 1, 2, 3)" src="https://cdn.freecodecamp.org/curriculum/project-euler/box-ball-system-1.gif" style="background-color: white; padding: 10px;" />

Така система називається системою коробок та м’ячів, або якщо коротко — СКМ.

Можна довести, що після значної кількості ходів система доходить до положення, де послідовні числа заповнених коробок не змінюються. У прикладі нижче послідовні числа заповнених коробок досягають [1, 2, 3], що назвемо кінцевим положенням.

<img class="img-responsive center-block" alt="чотири ходи з заповнених коробок [2, 2, 2] до кінцевого положення [1, 2, 3]" src="https://cdn.freecodecamp.org/curriculum/project-euler/box-ball-system-2.gif" style="background-color: white; padding: 10px;" />

Визначимо послідовність $\\{t_i\\}$:

$$\begin{align}   & s_0 = 290\\,797 \\\\
  & s_{k + 1} = {s_k}^2\bmod 50\\,515\\,093 \\\\ & t_k = (s_k\bmod 64) + 1 \end{align}$$

Починаючи з початкового розташування $(t_0, t_1, \ldots, t_{10})$, кінцевим положенням буде [1, 3, 10, 24, 51, 75].

Знайдіть кінцеве положення, починаючи з початкового розташування $(t_0, t_1, \ldots, t_{10\\,000\\,000})$.

Надайте відповідь у вигляді суми квадратів елементів кінцевого положення. Наприклад, якщо кінцевим положенням є [1, 2, 3], то відповіддю буде $14 (= 1^2 + 2^2 + 3^2)$.

# --hints--

`boxBallSystem()` має повернути `31591886008`.

```js
assert.strictEqual(boxBallSystem(), 31591886008);
```

# --seed--

## --seed-contents--

```js
function boxBallSystem() {

  return true;
}

boxBallSystem();
```

# --solutions--

```js
// solution required
```
